package com.AdvancedDemos.集合.单列集合;

import java.math.BigDecimal;
import java.util.*;

public class LearnHashSet_LinkedHashSet_TreeSet {
    public static void main(String[] args) {
        /**
         * 哈希值:就是一个int型的数值,Java中每个对象都有一个哈希值,
         * Object类提供了hashCode方法,返回对象自己的哈希值
         *
         * public int hashCode()  返回对象的哈希值
         *
         * 对同一对象多次调用hashCode方法返回的哈希值是相同的,
         * 不同对象,他们的哈希值一般不相同,但也可能会相同(哈希碰撞)
         * int范围只有-21亿~21亿,而java中可以创建45亿对象,所以有3亿对象的哈希值可能是相同的,一般而言是不会重复的
         */


        /**
         *  ArrayList 使用带参构造可以转 XXXSet ,
         */
        ArrayList<String> list = new ArrayList<>();
        list.add("1");
        list.add("1");
        list.add("java");
        list.add("java");
        list.add("2");
        list.add("2");
        list.add("hello");
        list.add("world");
        list.add("hello");
        System.out.println(list);
        //ArrayList转HashSet可以实现去重
        HashSet<String> hashSet = new HashSet<>(list);
        System.out.println(hashSet);
        //ArrayList转LinkedHashSet可以实现有序化,指添加顺序就是打印顺序
        LinkedHashSet<String> linkedHashSet = new LinkedHashSet<>(list);
        System.out.println(linkedHashSet);
        //ArrayList转TreeSet可以实现去重+排序(默认升序)
        TreeSet<String> treeSet = new TreeSet<>(list);
        System.out.println(treeSet);


////////////////////////////////////////////////////////////////

        //查看hashCode哈希值
        System.out.println("-----------------");
        Student1 stu1 = new Student1("猪八戒", 25, 169.6);
        Student1 stu2 = new Student1("庄周", 22, 170.1);
        //查看stu1的哈希值
        System.out.println(stu1.hashCode());//2093176254
        System.out.println(stu1.hashCode());//2093176254
        System.out.println(stu2.hashCode());//1854731462

        String str1 = new String("abc");
        String str2 = new String("acD");
        System.out.println(str1.hashCode());//96354
        System.out.println(str2.hashCode());//96354 发生了哈希碰撞

/////////////////////////////////////////////////////////////////
        /**
         * HashSet集合底层基于哈希表(即数组下挂链表/红黑树)实现,哈希表是一种增删改查数据,性能都较好的数据结构,因为只需要拿着哈希值对数组长度求余就可以随机访问,而插入删除直接下挂或者置为null即可
         *
         * 在JDK8之前,哈希表 = 数组 + 链表
         * JDK8之后,哈希表 = 数组 + 链表 + 红黑树
         *
         * Set<String> set = new HashSet<>();
         * set.add("数据1");
         * 创建HashSet对象后,第一次添加数据对象时,
         * ①默认创建一个长度为16的数组,默认加载因子为0.75,数组名table
         * ②使用元素的"哈希值"对"数组长度求余"计算出应存入的位置
         * ③判断当前位置是否为null,如果是null则直接存入
         * ④如果求余所得的位置不为null,表示已经有元素了,则调用equals方法进行比较,如果相等,则直接去重不存,如果不相等,则存入数组.
         * 具体存放而言,JDK8之前,将新元素放到当前位置,原来的老元素用链表下挂,JDK8之后,新元素会直接用链表或红黑树直接挂在老元素下面
         *
         * 随着数据添加,下挂链表会过过长,导致查询性能降低,需要进行数组扩容,默认加载因子是0.75,即数组占用到75%(16 * 0.75 = 12)后就会扩容,并不会等到完全填满16个数组位置才扩容,因为占满12个坑可能就已经下挂了很长的链表了,扩容会扩容到原数组的2倍,再把原数组中的数据全部转移到新数组中,但是即使是扩容数组,依然可能出现某一个数组元素下挂很长的链表导致查询效率降低,于是从JDK8开始,当链表长度超过8,且数组长度>=64时,自动将链表转成红黑树,红黑树是一颗二叉树,哈希值小的元素往根结点左边放,哈希值大的元素往根结点右边放,基于二分查找,查询效率大大提高
         */

        /**
         * 树结构中,度指每个结点的子结点个数,二叉树任意结点的度<=2,
         * 树高指树的总层数,
         * 开发中常用的是二叉查找树(又叫二叉排序树),它的特点是,小的存左子树,大的存右子树,重复的不存
         * 但二叉查找树会出现瘸子现象,数据全偏在一边,成为单链表,使得查询效率降低,改进办法是平衡二叉树(左右子树高度差不超过1),在保持二叉查找树特点不变的情况下,尽可能得降低树的高度,其实就是往另一边匀一些结点来降低树的高度,现在java中使用的都是平衡二叉树,
         * 而[红黑树]就是一种自平衡的平衡二叉树,底层有算法自动维护树的平衡和均匀,只需要知道红黑树是一种增删改查数据性能相对都较好的结构即可
         */

        /**
         * HashSet去重复时只会去除基本数据类型变量,并不会将内容相同的对象去除,原因是尽管内容相同,但并不是同一个对象,而不同对象的哈希值是不同的,导致对数组长度取余的结果不同,将存放在不同的数组元素中,而判重的equals对象,又只会对同一数组元素下挂的链表进行查重,所以当然是找不到重复的,两个对象都被保留在了HashSet中,
         * 想要去重相同内容对象,需要让两者的哈希值相同,再通过equals比较内容,就可以实现相同内容对象的去重,这就需要重写对象的hashCode()和equals()方法
         *
         */

        Set<Student1> stus = new HashSet<>();
        /*Student stu1 = new Student("猪八戒", 25, 169.6);
        Student stu2 = new Student("庄周", 22, 170.1);*/
        Student1 stu3 = new Student1("庄周", 22, 170.1);

        Student1 stu4 = new Student1("墨子", 18, 180.1);
        stus.add(stu1);
        stus.add(stu2);
        stus.add(stu3);
        stus.add(stu4);
        System.out.println("--------------");
        System.out.println(stu2.hashCode());
        System.out.println(stu3.hashCode());
        System.out.println("--------------");
        System.out.println(stus);//[Student{name='庄周', age=22, height=170.1}, Student{name='庄周', age=22, height=170.1}, Student{name='猪八戒', age=25, height=169.6}, Student{name='墨子', age=18, height=180.1}]
        // 没有重写equals和hashcode方法前两个对象内容一样,HashSet并没有去重,重写后
        // [Student{name='庄周', age=22, height=170.1}, Student{name='墨子', age=18, height=180.1}, Student{name='猪八戒', age=25, height=169.6}]


//////////////////////////////////////////////////////////////
        /**
         * LinkedHashSet底层与HashSet一样依然是基于哈希表(数组,链表,红黑树)实现的,但是它的每个元素都额外多了一个双链表的机制记录它前后元素的位置,通过多占用一些内存来实现有序访问的特点
         */
///////////////////////////////////////////////////////////////


        /*
          TreeSet 特点是不重复,无索引,可排序(默认升序排序,按照元素大小,由小到大),底层是基于红黑树实现的排序,当第一次add时,会在底层建一颗红黑树,让第一个元素成为根结点,后续添加元素小的往左子树放,大的往右子树放,遇到重复的不放*/

        System.out.println("----------------");
        Set<Integer> treeSet2 = new TreeSet<>();
        treeSet2.add(6);
        treeSet2.add(5);
        treeSet2.add(5);
        treeSet2.add(7);
        System.out.println(treeSet2);//[5, 6, 7]

        /* 对于数值类型Integer Double 默认按照数值本身的大小进行升序排序,对于字符串类型,默认按照首字符的编号升序排序
          对于自定义类型如Student对象,TreeSet默认是无法直接排序的
         */

/**
 *如果TreeSet的泛型是自定义类,那么必须指定排序规则,支持如下两种方式来指定比较规则:
 * ①让自定义类如Student实现Comparable<Student>接口(拥有自然排序能力),并重写 public int compareTo(Student o) 方法,来指定比较规则
 * 默认升序排序约定:当认为this > o 时 返回正整数 ;
 * 当认为this < o 时 返回负整数 ;
 * 当认为this == o 时 返回整数0 ;
 * 函数体中应当自己实现具体某个属性的比较规则,来决定大小,返回对应的整数,
 * 还可以实现多属性排序,优先按照某一属性排序,当第一属性相同时,按照第二属性排序 (与Arrays.sort排序自定义类时操作相同,详见Arrays类.java)
 *
 * ②除了使用自然排序,还可以通过调用TreeSet集合有参构造器,使用比较器Comparator接口的匿名内部类对象作为实参,重写compare函数来指定排序规则(与Arrays.sort相同)
 *
 * 如果同时使用两种方式自定义排序规则,会优先使用Comparator比较器排序,其优先级更高,高于自定义类实现Comparable接口,甚至可以覆盖系统String默认按照ACSII值排序的规则
 */

        System.out.println("----------------");
        Set<Student1> students = new TreeSet<>();//自动调用实现了Comparable<Student>接口的Student对象中重写的compareTo方法,实现自定义对象的升序排序
        students.add(new Student1("蜘蛛精", 23, 169.7));
        students.add(new Student1("紫霞", 22, 169.8));
        students.add(new Student1("至尊宝", 26, 165.5));
        students.add(new Student1("牛魔王", 22, 182.5));
        System.out.println(students);//[Student{name='紫霞', age=22, height=169.8}, Student{name='蜘蛛精', age=23, height=169.7}, Student{name='至尊宝', age=26, height=165.5}]  发现牛魔王数据没了,因为年龄与紫霞的22相同compareTo方法返回值是0,于是被认为是重复对象而删除了,可以通过多属性排序,优先按照某一属性排序,当第一属性相同时,按照第二属性排序来避免因为一个属性相同就被删除

        students = new TreeSet<>(/*new Comparator<Student>() {
            @Override
            public int compare(Student o1, Student o2) {
                BigDecimal b1 = BigDecimal.valueOf(o1.getHeight());
                BigDecimal b2 = BigDecimal.valueOf(o2.getHeight());
                return b1.compareTo(b2);//返回值:-1, 0, or 1 as this BigDecimal is numerically less than, equal to, or greater than val.
//                或者
//                return Double.compare(o1.getHeight(), o2.getHeight());
            }
        }*/
                (o1, o2) -> {//简化为Lambda表达式
                    BigDecimal b1 = BigDecimal.valueOf(o1.getHeight());
                    BigDecimal b2 = BigDecimal.valueOf(o2.getHeight());
                    return b1.compareTo(b2);//返回值:-1, 0, or 1 as this BigDecimal is numerically less than, equal to, or greater than val.
//                或者
//                return Double.compare(o1.getHeight(), o2.getHeight());
                }
        );
                /*public static int compare(double d1, double d2) {
        if (d1 < d2)
            return -1;           // Neither val is NaN, thisVal is smaller
        if (d1 > d2)
            return 1;            // Neither val is NaN, thisVal is larger

        // Cannot use doubleToRawLongBits because of possibility of NaNs.
        long thisBits    = Double.doubleToLongBits(d1);
        long anotherBits = Double.doubleToLongBits(d2);

        return (thisBits == anotherBits ?  0 : // Values are equal
                (thisBits < anotherBits ? -1 : // (-0.0, 0.0) or (!NaN, NaN)
                 1));                          // (0.0, -0.0) or (NaN, !NaN)
    }
*/

        students.add(new Student1("蜘蛛精", 23, 169.7));
        students.add(new Student1("紫霞", 22, 165.5));
        students.add(new Student1("至尊宝", 26, 165.5));
        students.add(new Student1("牛魔王", 22, 182.5));
        System.out.println("----------------");
        System.out.println(students);


        System.out.println("----------------");
        //实现多属性排序,优先按照某一属性排序,当第一属性相同时,按照第二属性排序来避免因为一个属性相同就被删除
        TreeSet<String> treeSet1 = new TreeSet<>(new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                int result = o2.length() - o1.length();//按照字符串长度由大到小逆序排序
                if (result == 0) {//当长度相同时
                    result = o2.compareTo(o1);//按照ASCII码值逆序排序
                }
                return result;
            }
        });
        treeSet1.add("1234");
        treeSet1.add("1232");
        treeSet1.add("12345");
        treeSet1.add("12445");
        treeSet1.add("123456");
        treeSet1.add("123465");
        treeSet1.add("123");
        treeSet1.add("12");
        treeSet1.add("21");
        treeSet1.add("2134");
        System.out.println(treeSet1);


    }
}

class Student implements Comparable<Student> {

    private String name;
    private int age;
    private double height;

    public Student() {
    }

    public Student(String name, int age, double height) {
        this.name = name;
        this.age = age;
        this.height = height;
    }

    @Override
    public int compareTo(Student o) {
        //this与o进行比较,默认升序
        //如果 返回正整数 认为this > o
        //如果 返回负整数 认为this < o
        //如果 返回整数0 认为this == o
        return this.age - o.age;//升序
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Student student = (Student) o;
        return age == student.getHeight() && Double.compare(student.getHeight(), height) == 0 && Objects.equals(name, student.getName());
    }//只要两个对象内容一样,就返回true

    @Override
    public int hashCode() {
        return Objects.hash(name, age, height);
    }//只要两个对象内容一样,返回的哈希值就是一样的,因为是根据姓名,年龄,身高来计算哈希值的

    @Override
    public String toString() {
        return "Student{" + "name='" + name + '\'' + ", age=" + age + ", height=" + height + '}';
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public int getAge() {
        return age;
    }

    public void setAge(int age) {
        this.age = age;
    }

    public double getHeight() {
        return height;
    }

    public void setHeight(double height) {
        this.height = height;
    }


}

/**
 * 何时使用何种集合容器?
 * 1.如果希望记住元素的添加顺序,需要存储重复的元素,又要频繁的根据索引查询数据
 * 用ArrayList(有序,可重复,有索引),底层基于数组 (常用)
 * <p>
 * 2.如果希望记住元素的添加顺序,且增删首尾数据的情况较多?
 * 用LinkedList(有序,可重复,有索引),底层基于双链表实现的
 * <p>
 * 3.如果不在意元素顺序,也没有重复元素需要存储,只希望增删改查都快?
 * 用HashSet集合(无序,不重复,无索引),底层基于哈希表实现的 (常用)
 * <p>
 * 4.如果希望记住元素的添加顺序,也没有重复元素需要存储,且希望增删改查都快?
 * 用LinkedHashSet集合(有序,不重复,无索引),底层基于哈希表和双链表
 * <p>
 * 5.如果要对元素进行排序,也没有重复元素需要存储?且希望增删改查都快?
 * 用TreeSet集合,基于红黑树实现
 */
